FWCG, 2022
Sushovan Majhi, UC Berkeley
Carola Wenk, Tulane University
A combinatorial graph \(G=(V,E)\) is called geometric if
IAM (Riesen and Bunke 2008)
Source: mapconstruction.org (Ahmed et al. since 2013)
Given two geometric graphs \(G, H\):
\[GED(G,H):=\inf cost(P),\] where the infimum is taken over all edit paths from \(G\) to \(H\).
GED is a metric for positive \(C_V, C_E\).
\[ \cost(\pi)= \underbrace{\sum_{\substack{u\in V^G \\ \pi(u)\neq\epsilon_V}} C_V\lvert u-\pi(u)|}_\text{vertex translations} + \underbrace{\sum_{\substack{e\in E^G \\ \pi(e)\neq\epsilon_E}} C_E\big||e|-|\pi(e)|\big|}_\text{edge translations} + \underbrace{\sum_{\substack{e\in E^G \\ \pi(e)=\epsilon_E}} C_E|e|} _\text{edge deletions} + \underbrace{\sum_{\substack{f\in E^H \\ \pi^{-1}(f)=\epsilon_E}} C_E|f|} _\text{edge deletions} \]
\[ \ggd(G,H)\eqdef\min_{\pi\in\Pi(G,H)}\cost(\pi). \]
\[ \ggd(G,H)\leq\ged(G,H)\leq\left(1+\Delta\frac{C_E}{C_V}\right)\ggd(G,H) \]
Say hi: smajhi@berkeley.edu